package 中等.二分查找;

import java.util.Arrays;
import java.util.List;

/**
 * 假设你是一家合金制造公司的老板，你的公司使用多种金属来制造合金。现在共有 n 种不同
 * 类型的金属可以使用，并且你可以使用 k 台机器来制造合金。每台机器都需要特定数量的每种金属来创建合金。
 * 对于第 i 台机器而言，创建合金需要 composition[i][j] 份 j 类型金属。最初，你拥有
 * stock[i] 份 i 类型金属，而每购入一份 i 类型金属需要花费 cost[i] 的金钱。
 * 给你整数 n、k、budget，下标从 1 开始的二维数组 composition，两个下标从 1 开始的数组\
 * stock 和 cost，请你在预算不超过 budget 金钱的前提下，最大化 公司制造合金的数量。
 * 所有合金都需要由同一台机器制造。
 * 返回公司可以制造的最大合金数。
 *
 * @ https://leetcode.cn/problems/maximum-number-of-alloys/
 * @date 2024/08/24
 */
public class 最大合金数_2861 {

    public static void main(String[] args) {

        System.out.println(maxNumberOfAlloys(3, 2, 15,
                Arrays.asList(
                        Arrays.asList(1, 1, 1),
                        Arrays.asList(1, 1, 10)

                ),
                Arrays.asList(0, 0, 100),
                Arrays.asList(1, 2, 3)
        ));

    }

    /**
     * 二分答案
     * 因为存在库存，计算花费多少预算的时候，需要遍历每个金属，需要的份数-库存份数，得出总预算
     */
    public static int maxNumberOfAlloys(int n, int k, int budget, List<List<Integer>> composition, List<Integer> stock, List<Integer> cost) {
        int ans = 0;

        for (List<Integer> composit : composition) {

            int minNum = Integer.MAX_VALUE;
            for (int i = 0; i < composit.size(); i++) {
                minNum = Math.min(minNum, (budget / cost.get(i) + stock.get(i)) / composit.get(i));
            }

            int left = 0, right = minNum;
            int cur = 0;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (getBudget(composit, stock, cost, mid) <= budget) {
                    cur = mid;
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
            ans = Math.max(ans, cur);

        }
        return ans;
    }

    private static int getBudget(List<Integer> composit, List<Integer> stock, List<Integer> cost, int number) {
        int budget = 0;
        for (int i = 0; i < composit.size(); i++) {
            // 需要的购买的份数-库存数
            int need = number * composit.get(i) - stock.get(i);
            if (need <= 0) {
                continue;
            }
            budget += need * cost.get(i);
        }
        return budget;
    }

}
